import java.util.HashMap;
import java.util.Map;

public class test {
    public static void main(String[] args) {
        String str1 = "abcfabc";
        String str2 = "afkafk";

        System.out.println("最长的重复子串（str1）: " + findLongestDuplicateSubstring(str1));
        System.out.println("最长的重复子串（str2）: " + findLongestDuplicateSubstring(str2));
    }

    public static String findLongestDuplicateSubstring(String s) {
        // 使用滚动哈希的方法来查找最长的重复子串
        int n = s.length();
        long[] pow = new long[n + 1];
        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow[i] = (pow[i - 1] * 26) % 101;
        }

        long mod = 101;
        long base = 27;
        long hash = 0;
        long maxHash = 0;
        int maxLength = 0;
        Map<Long, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            hash = (hash * base + (s.charAt(i) - 'a' + 1)) % mod;
            if (i >= n - maxLength) {
                if (hash == maxHash && s.substring(i - maxLength, i + 1).equals(s.substring(0, maxLength + 1))) {
                    return s.substring(0, maxLength + 1);
                }
                maxHash = hash;
                map.clear();
                map.put(hash, 0);
            }
            if (i >= n - maxLength + 1) {
                map.put(hash, i);
                hash = (hash - (s.charAt(i - maxLength) - 'a' + 1) * pow[maxLength + 1] + mod) % mod;
                if (map.containsKey(hash)) {
                    int start = map.get(hash);
                    if (i - start < n - maxLength) {
                        maxLength = i - start;
                        maxHash = hash;
                        map.clear();
                        map.put(hash, i);
                    }
                }
            }
        }
        return s.substring(0, maxLength + 1);
    }
}